/*
题目: 使数组可以被整除的最少删除次数
给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。

请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素，返回 -1 。

如果 y % x == 0 ，那么我们说整数 x 整除 y 。
https://leetcode.cn/contest/weekly-contest-302/problems/minimum-deletions-to-make-array-divisible/
 */
public class MinOperations {
    public int minOperations(int[] nums, int[] numsDivide) {
        //先求出numsDivide数组的最小因子
        int prev = numsDivide[0];
        for (int i = 1; i < numsDivide.length; i ++) {
            if (prev == 1) {
                break;  //最小因子
            }
            prev = gcd(numsDivide[i], prev);
        }
        //循环结束, prev就是numsDivide中的最小因子

        Arrays.sort(nums);
        int deleteCnt = 0; //删除次数
        for (int x : nums) {
            if (prev % x == 0) {
                return deleteCnt;
            }

            if (prev < x) {
                return -1;
            }
            deleteCnt ++;
        }
        return -1;
    }

    private int gcd(int a, int b) {
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }
}
